/*
 * Naive.cpp
 *
 *  Created on: 14-06-2013
 *      Author: Krzychu
 */

#include "ShiftOr.h"

#include "../Structures/Config.h"

#define MAX(a, b) (a > b) ? a : b
#define ASIZE 255

ShiftOr::ShiftOr()
{

}

ShiftOr::~ShiftOr()
{

}

std::string ShiftOr::getName()
{
	return "Shift Or";
}

int preSo(std::string pattern, unsigned int S[])
{
	unsigned int lim;
	int patternSize = pattern.size();

	for (int i = 0; i < ASIZE; i++)
	{
		S[i] = ~0;
	}

	for (int i = lim = 0, j = 1; i < patternSize; i++, j <<= 1)
	{
		S[(unsigned int)pattern[i]] &= ~j;
		lim |= j;
	}

	lim = ~(lim >> 1);

	return(lim);
}

searchResult ShiftOr::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	unsigned int lim, state;

	unsigned int* S = new unsigned int[MAX(patternSize, ASIZE)];
	int j;

	lim = preSo(pattern, S);

	for (state = ~0, j = 0; j < textSize; ++j)
	{
		result.iterationsTaken++;
		state = (state << 1) | S[(unsigned int)text[j]];
		if (state < lim)
		{
			result.positionsFound.push_back(j - patternSize + 1);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
		}
	}

	return result;
}

